package wtx.leetcode;

import java.util.Arrays;

/**
 * Suppose an array sorted in ascending order is rotated at some pivot unknown
 * to you beforehand.
 * 
 * (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
 * 
 * You are given a target value to search. If found in the array return its
 * index, otherwise return -1.
 * 
 * You may assume no duplicate exists in the array.
 * 
 * Your algorithm's runtime complexity must be in the order of O(log n).
 * 
 * Example 1:
 * 
 * Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 
 * 
 * Example 2:
 * 
 * Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
 */
public final class App {
  private int searchHelper(int[] nums, int left, int right, int target) {
    if (nums == null || nums.length < 1) return -1;
    if (right - left == 1) {
      return nums[left] == target ? left : -1;
    }
    int mid = (left+right)/2;
      // at right half
    if (nums[left] > target) {
      if (nums[left] > nums[mid]) {
        // element at right of mid is sorted
        if (nums[mid] <= target) {
          return Arrays.binarySearch(nums, mid, right, target);
        } else {
          return searchHelper(nums, left, mid, target);
        }
      } else {
        return searchHelper(nums, mid, right, target);
      } 
    } else {
      if (nums[left] == target) {
        return left;
      } else {
        // left < target
        // at left half[left < target ]
        if (nums[left] < nums[mid]) {
          // mid <= target, at right of mid
          if (nums[mid] > target) {
            return Arrays.binarySearch(nums, left, mid, target);
          } else {
            return searchHelper(nums, mid, right, target);
          }
        } else {
          return searchHelper(nums, left, mid, target);
        }
      }
    }
  }
  public int search(int[] nums, int target) {
    int r = searchHelper(nums, 0, nums.length, target);
    return r >= 0 ? r : -1;
  }
  /**
   * Says hello to the world.
   * 
   * @param args
   *               The arguments of the program.
   */
  public static void main(String[] args) {
    int[] nums = {4,5,6,7,0,1,2};
    App app = new App();
    System.out.println(app.search(nums, 7));
  }
}
